1. Field of the Invention
The invention relates to an interleaving/de-interleaving and corresponding error correcting coding/decoding methods, and more particularly to a highly efficient interleaving/de-interleaving method for high turbo coding/decoding performance.
2. Description of the Related Art
Turbo code, also known as the parallel concatenated convolutional code, is impressive with the near Shannon limit performance A rate-⅓ turbo codeword is formed by the systematic data along with two parity checks, which are encoded from the information in original order and in permuted order, respectively. A conventional turbo decoder consists primarily of one soft-in/soft-out (SISO) decoder for calculating soft value, wherein codewords received and temporary results are stored in a memory. For each component code, the SISO decoder can utilize a maximum a posteriori probability (MAP) algorithm to obtain a log-likelihood ration (LLR) and extrinsic information. The LLR is used to make decisions, and the extrinsic information is treated as the a priori estimation for the other component code. The soft value computation of each component code is called, one half-iteration, and two successive half-iterations constitute of a complete iteration. The decoding flow alternates between an original component and a permuted component until certain stopping criterion is satisfied.
However, some characteristics of turbo codes combine to make the associated decoders more difficult to implement in an integrated circuit. These characteristics include large frame sizes, the use of repeated decoding steps that incorporate extrinsic information, and the use of a pseudo random interleaver for generating interleaved versions of the transmitted information and extrinsic information used during encoding and decoding. Additionally, many turbo-coding schemes require a sufficiently high degree of randomness in the psuedo random interleaver such that the sequence must be stored in memory rather than calculated on the fly. This combination of characteristics causes turbo codes to require, in general, greater processing resources than other forward error correction coding techniques. For example, the use of repeated decoding steps increases the decoding time.
FIG. 1 is a schematic diagram showing a conventional decoding process of a turbo code SISO decoder. The SISO decoder includes a plurality of buffers, such as the input buffers and α buffer as shown, for temporarily storing the input codewords to be decoded and the calculation results of the forward path metric α. The SISO decoder further includes a plurality of calculation units, such as the branch metric units for calculating the branch metrics, β ACS for calculating the backward path metric β, and βd ACS for calculating the dummy backward path metric βd. The LLR unit generates the log-likelihood ration (LLR) calculation result for calculating the soft value based on the forward and backward path metrics α and β. FIG. 2 is a schematic diagram showing the decoding flow of the conventional SISO decoder for obtaining the branch metrics and path metrics, wherein the blocks filled with gray color represent calculations of a half iteration for permuted sequences. As previously described, the decoding flow alternates between the original component and the permuted component until certain stopping criterion is satisfied. The conventional SISO decoder usually adopts the sliding window method to calculate the path metric and LLR for less overhead. The time required in each half-iteration can be defined as follows: δa is the pipeline delay, δb is the memory access time, τa is the time to get the necessary metrics for LLR in the first window W0, and τb is the time to derive the LLR results and decisions of all windows. Since it takes τb out of the total execution time to generate outputs, the operating efficiency η can be derived by:
                    η        =                              τ            b                                              τ              a                        +                          τ              b                        +                          δ              a                        +                          δ              b                                                          Eq        .                                  ⁢                  (          1          )                    where the value of τa, τb, δa, and δb are affected by window length and decoder architecture. For the decoding schedule of a conventional SISO decoder shown in FIG. 1, the execution periods for two windows can be expressed as:
                    {                                                                              0                  ≤                                      δ                    a                                                  ,                                                      δ                    b                                    ≤                  L                                                                                                                          2                  ⁢                  L                                ≤                                  τ                  a                                ≤                                  3                  ⁢                  L                                                                                                                          τ                  b                                =                                  2                  ⁢                  L                                                                                        Eq        .                                  ⁢                  (          2          )                    For simplicity, it is assumed that the SISO decoder can process one trellis stage per cycle. In addition, the window length is represented as L here. When the window number is K (=N/L, N is the total bit number), only τb grows to K×L cycles, and the other terms remain unchanged. Here we assume the summation of δa, δb and τa is approximated to 3 L cycles, and then η will be
      K          K      +      3        .It is obvious that a smaller K results in lower operating efficiency η. Further, because corresponding extrinsic information is not available until completion of a previous half iteration, the conventional SISO decoder has to wait for completion of a current half iteration and then start a new half iteration. In other words, a new half iteration cannot be started while a current half iteration is still in process. Otherwise, undesired idle time of the calculation units would occur.
FIG. 3 is a timing diagram showing the active periods of the calculating units in the conventional SISO decoder as shown in FIG. 1, where the Wi stands for the i-th window, and in each window, the dummy backward path metric βd, forward path metric α, backward path metric β and LLR are computed successively. As shown in FIG. 3, the idle periods of the calculating units in the conventional SISO decoder are actually longer than the active periods, causing low decoding efficiency.
To solve the above-mentioned low efficiency problems, a novel turbo SISO decoding method in company with corresponding interleaving/de-interleaving techniques to provide higher decoding performance and greater efficiency is highly required.